package com.tys.algorithm.bak.code1;

import java.util.HashMap;

public class Code35_TrieTree2 {

    //方法1：固定数组
    // 前缀树节点类型
    public static class Node1 {
        public int pass; //通过数
        public int end;  //结尾数
        public Node1[] nexts; //固定数组

        public Node1() {
            pass = 0;
            end = 0;
            //nexts[i]==null为不存在
            //nexts[i]!=null存在
            nexts = new Node1[26]; //小写字母26个
        }
    }

    public static class Trie1 {
        //头节点
        private Node1 root;

        public Trie1() {
            root = new Node1();
        }

        //字符串加入前缀树
        public void insert(String word) {
            if (word == null) { //为空返回
                return;
            }
            char[] chs = word.toCharArray(); //转字符数组
            Node1 node = root; //保留头
            node.pass++; //通过加1
            int index = 0; //固定数组索引
            for (int i = 0; i < chs.length; i++) { // 从左往右遍历字符
                index = chs[i] - 'a'; // 由字符，对应成走向哪条路
                if (node.nexts[index] == null) { //null则建立新节点
                    node.nexts[index] = new Node1();
                }
                node = node.nexts[index]; //跳下一个
                node.pass++; //通过加1
            }
            node.end++; //结尾加1
        }

        //删除字符串
        public void delete(String word) {
            //判断字符串是否存在
            if (search(word) != 0) {
                //转字符数组
                char[] chs = word.toCharArray();
                Node1 node = root; //头
                node.pass--; //通过减1
                int index = 0; //固定数组索引
                for (int i = 0; i < chs.length; i++) {
                    index = chs[i] - 'a'; //计算索引
                    //index位置通过数pass减1
                    //pass为0则将节点置空null
                    if (--node.nexts[index].pass == 0) {
                        node.nexts[index] = null; //节点置空防止内存泄漏
                        return;
                    }
                    node = node.nexts[index]; //跳下一个
                }
                node.end--; //结尾减1
            }
        }

        // word这个单词之前加入过几次
        public int search(String word) {
            //字符串为空返回
            if (word == null) {
                return 0;
            }
            //转字符数组
            char[] chs = word.toCharArray();
            Node1 node = root; //头
            int index = 0; //固定数组索引
            for (int i = 0; i < chs.length; i++) {
                index = chs[i] - 'a'; //计算索引
                if (node.nexts[index] == null) { //为空返回0
                    return 0;
                }
                node = node.nexts[index]; //跳下一个
            }
            return node.end; //返回结尾数
        }

        // 所有加入的字符串中，有几个是以pre这个字符串作为前缀的
        public int prefixNumber(String pre) {
            if (pre == null) {
                return 0;
            }
            char[] chs = pre.toCharArray();
            Node1 node = root;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = chs[i] - 'a';
                if (node.nexts[index] == null) {
                    return 0;
                }
                node = node.nexts[index];
            }
            return node.pass; //返回通过数
        }
    }

    //方法2：哈希表，字符种类很多时使用
    public static class Node2 {
        public int pass; //通过数
        public int end;  //结尾数
        public HashMap<Integer, Node2> nexts; //节点哈希可以存储很多

        public Node2() {
            pass = 0;
            end = 0;
            nexts = new HashMap<>();
        }
    }

    public static class Trie2 {
        private Node2 root; //头节点

        public Trie2() {
            root = new Node2();
        }

        //字符串加入
        public void insert(String word) {
            if (word == null) {
                return;
            }
            //转字符数组
            char[] chs = word.toCharArray();
            Node2 node = root; //头
            node.pass++; //通过数加1
            int index = 0; //当前字符
            for (int i = 0; i < chs.length; i++) {
                index = (int) chs[i]; //当前字符
                //当前字符哈希表中不存在，新建节点插入哈希表
                if (!node.nexts.containsKey(index)) {
                    node.nexts.put(index, new Node2());
                }
                //node跳当前字符节点
                node = node.nexts.get(index);
                node.pass++; //通过加1
            }
            node.end++; //结尾加1
        }

        //字符串删除
        public void delete(String word) {
            if (search(word) != 0) {
                char[] chs = word.toCharArray();
                Node2 node = root;
                node.pass--;
                int index = 0;
                for (int i = 0; i < chs.length; i++) {
                    index = (int) chs[i];
                    //当前字符pass减1
                    if (--node.nexts.get(index).pass == 0) {
                        //pass等于0则删除当前字符节点，防止内存泄漏
                        node.nexts.remove(index);
                        return;
                    }
                    //得到当前字符节点
                    node = node.nexts.get(index);
                }
                node.end--; //结尾减1
            }
        }

        // word这个单词之前加入过几次
        public int search(String word) {
            if (word == null) {
                return 0;
            }
            char[] chs = word.toCharArray();
            Node2 node = root;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = (int) chs[i];
                //当前字符不在哈希表中返回0，没找到
                if (!node.nexts.containsKey(index)) {
                    return 0;
                }
                node = node.nexts.get(index);
            }
            return node.end; //找到返回结尾数
        }

        // 所有加入的字符串中，有几个是以pre这个字符串作为前缀的
        public int prefixNumber(String pre) {
            if (pre == null) {
                return 0;
            }
            char[] chs = pre.toCharArray();
            Node2 node = root;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = (int) chs[i];
                //没找到：当前字符不在哈希表中
                if (!node.nexts.containsKey(index)) {
                    return 0;
                }
                node = node.nexts.get(index);
            }
            return node.pass; //找到返回通过数
        }
    }

    //测试：哈希
    public static class Right {
        //哈希表
        private HashMap<String, Integer> box;

        public Right() {
            box = new HashMap<>();
        }

        //插入哈希表
        public void insert(String word) {
            //字符串不存在则插入哈希表
            if (!box.containsKey(word)) {
                box.put(word, 1);
            } else {
                //字符串存在则值加1
                box.put(word, box.get(word) + 1);
            }
        }

        //删除字符串
        public void delete(String word) {
            //字符串存在
            if (box.containsKey(word)) {

                if (box.get(word) == 1) { //最后一个
                    box.remove(word); //删除字符串
                } else {
                    //不是最后一个值减1
                    box.put(word, box.get(word) - 1);
                }
            }
        }

        //字符串是否存在
        public int search(String word) {
            if (!box.containsKey(word)) {
                return 0; //哈希表中没有返回0
            } else {
                return box.get(word); //存在返回数量
            }
        }

        //字符串作为前缀几个
        public int prefixNumber(String pre) {
            int count = 0;
            //遍历使用startWith方法找到哈希表中key的
            for (String cur : box.keySet()) {
                if (cur.startsWith(pre)) { //判断是否是以pre开始
                    count += box.get(cur); //通过数量累加
                }
            }
            return count;
        }
    }

    // for test
    public static String generateRandomString(int strLen) {
        char[] ans = new char[(int) (Math.random() * strLen) + 1];
        for (int i = 0; i < ans.length; i++) {
            int value = (int) (Math.random() * 6);
            ans[i] = (char) (97 + value);
        }
        return String.valueOf(ans);
    }

    // for test
    public static String[] generateRandomStringArray(int arrLen, int strLen) {
        String[] ans = new String[(int) (Math.random() * arrLen) + 1];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = generateRandomString(strLen);
        }
        return ans;
    }

    public static void printArray(String[] arr) {
        for (String str : arr) {
            System.out.print(str + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int arrLen = 100;
        int strLen = 20;
        int testTimes = 100000;
        for (int i = 0; i < testTimes; i++) {
            String[] arr = generateRandomStringArray(arrLen, strLen);
            Trie1 trie1 = new Trie1();
            Trie2 trie2 = new Trie2();
            Right right = new Right();
            for (int j = 0; j < arr.length; j++) {
                double decide = Math.random();
                if (decide < 0.25) {
                    trie1.insert(arr[j]);
                    trie2.insert(arr[j]);
                    right.insert(arr[j]);
                } else if (decide < 0.5) {
                    trie1.delete(arr[j]);
                    trie2.delete(arr[j]);
                    right.delete(arr[j]);
                } else if (decide < 0.75) {
                    int ans1 = trie1.search(arr[j]);
                    int ans2 = trie2.search(arr[j]);
                    int ans3 = right.search(arr[j]);
                    if (ans1 != ans2 || ans2 != ans3) {
                        System.out.println("Oops1!");
                        System.out.println("ans1:" + ans1 + " ans2:" + ans2 + " ans3:" + ans3);
                        printArray(arr);

                        return;
                    }
                } else {
                    int ans1 = trie1.prefixNumber(arr[j]);
                    int ans2 = trie2.prefixNumber(arr[j]);
                    int ans3 = right.prefixNumber(arr[j]);
                    if (ans1 != ans2 || ans2 != ans3) {
                        System.out.println("Oops2!");
                        System.out.println("ans1:" + ans1 + " ans2:" + ans2 + " ans3:" + ans3);
                        printArray(arr);

                        return;
                    }
                }
            }
        }
        System.out.println("finish!");

    }

}
